package leetcode.number;

/**
 * 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：c = 5
 * 输出：true
 * 解释：1 * 1 + 2 * 2 = 5
 * 示例 2：
 * <p>
 * 输入：c = 3
 * 输出：false
 * 示例 3：
 * <p>
 * 输入：c = 4
 * 输出：true
 * 示例 4：
 * <p>
 * 输入：c = 2
 * 输出：true
 * 示例 5：
 * <p>
 * 输入：c = 1
 * 输出：true
 *  
 * <p>
 * 提示：
 * <p>
 * 0 <= c <= 231 - 1
 */
public class JudgeSquareSum {

    public static boolean judgeSquareSum(int c) {
//        for (long index = 0; index <= c; index++) {
//            if (index * index > c) {
//                continue;
//            }
//            for (long flag = 0; flag <= c; flag++) {
//                if (flag * flag > c) {
//                    break;
//                }
//                long num = index * index + flag * flag;
//                if (num == c) {
//                    return true;
//                } else if (num > c) {
//                    break;
//                }
//            }
//        }
//        return false;
        /**
         * Math.sqrt();平方根函数
         */
        long a = 0;
        long b = (long) Math.sqrt(c);
        /**
         * a² + b² = c
         * a² + b² > c b--
         * a² + b² < c a++
         */
        while (a<=b) {
            long num = a * a + b * b;
            if (num == c) {
                return true;
            } else if (num > c) {
                b--;
            } else if (num < c) {
                a++;
            }

        }
        return false;
    }

}
